/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/count-primes
   @Language: C++
   @Datetime: 19-05-27 11:29
   */

// Method 1, prime selection, Time 302ms
class Solution {
public:
	/**
	 * @param n: a integer
	 * @return: return a integer
	 */
	int countPrimes(int n) {
		// write your code here
		vector<bool> primes(n,true);
		int count=0;
		for(int i=2; i<n; ++i){
			if(primes[i]){
				++count;
				for(int j=i+i; j<n; j+=i)
					primes[j]=false;
			}
		}
		return count;
	}
};

// Method 2, prime selection2, Time 302ms
class Solution {
public:
	/**
	 * @param n: a integer
	 * @return: return a integer
	 */
	int countPrimes(int n) {
		// write your code here
		vector<bool> primes(n,true);
		int count=0;
		for(int i=2; i<n; ++i){
			if(primes[i]){
				++count;
				for(int j=2; i*j<n; ++j)
					primes[i*j]=false;
			}
		}
		return count;
	}
};
